﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TSP
{
    /// <summary>
    /// Generator grafów losowych
    /// </summary>
    public class Generator
        {

        private System.Random rand;

        /// <summary>
        /// Tworzy generator grafów
        /// </summary>
        /// <param name="seed">ziarno początkowe generatora, <b>parametr opcjonalny, wartość domyślna 0</b></param>
        /// <remarks>
        /// Jeśli <b>seed==0</b> to korzysta z czasu systemowego do inicjowania ziarna generatora.
        /// </remarks>
        public Generator(int seed = 0)
            {
            rand = ( seed==0 ) ? new System.Random() : new System.Random(seed) ;
            }

        /// <summary>
        /// Ustawia ziarno generatora grafów
        /// </summary>
        /// <param name="seed">nowe ziarno początkowe</param>
        public void SetSeed(int seed)
            {
            rand = new System.Random(seed) ;
            }

        /// <summary>
        /// Tworzy nowy graf uzyskany w wyniku losowej permutacji wierzchołków danego grafu
        /// </summary>
        /// <param name="g">Zadany graf</param>
        /// <returns>Wynikowy graf</returns>
        public IGraph Permute(IGraph g)
            {
            int i, k;
            int n = g.VerticesCount;
            int[] perm = new int[n];
            IGraph g2 = g.IsolatedVerticesGraph();
            var remaining = new System.Collections.Generic.List<int>(n);
            for ( i=0 ; i<n ; ++i )
                remaining.Add(i);
            for ( i=0 ; i<n ; ++i )
                {
                k = rand.Next(n-i);
                perm[i] = remaining[k];
                remaining.RemoveAt(k);
                }
            for ( i=0 ; i<n ; ++i )
                foreach ( Edge e in g.OutEdges(i) )
                    g2.AddEdge(perm[e.from], perm[e.to], e.weight);
            return g2;
            }
    
        /// <summary>
        /// Tworzy ważony graf nieskierowany
        /// </summary>
        /// <param name="tg">Sposób reprezentacji grafu</param>
        /// <param name="n">Liczba wierzchołków</param>
        /// <param name="density">Prawdopodobieństwo istnienia krawędzi</param>
        /// <param name="wMin">Dolna granica wagi krawędzi</param>
        /// <param name="wMax">Górna granica wagi krawędzi</param>
        /// <returns>Utworzony graf</returns>
        /// <remarks>
        /// Tworzony graf nie zawiera pętli, prawdopodonieństwo istnienia krawędzi pomiedzy dowolnymi wierzchołkami wynosi <i>density</i>.<br/>
        /// Oczekiwana liczba krawędzi wynosi <i>density</i>*n*(n-1)/2<br/>
        /// Wagi krawędzi są losowymi liczbami całkowitymi (rozkład jednostajny) z zakresu <i>wMin</i>..<i>wMax</i> (włącznie).<br/>
        /// Gęstość <i>density</i> musi być z przedziału [0,1].
        /// </remarks>
        public IGraph UndirectedGraph(System.Type tg, int n, double density, int wMin, int wMax)
            {
            if ( density<0 || density>1 || wMin>wMax )
                throw new System.ArgumentException("Invalid random graph generator argument");
            ++wMax;
            IGraph g = Graph.IsolatedVerticesGraph(false,n,tg);
            for ( int i=0 ; i<n ; ++i )
                for ( int j=i+1 ; j<n ; ++j)
                    if ( rand.NextDouble()<density)
                        g.AddEdge(i,j,rand.Next(wMin,wMax));
            return g;
            }

        /// <summary>
        /// Tworzy nieważony graf nieskierowany
        /// </summary>
        /// <param name="tg">Sposób reprezentacji grafu</param>
        /// <param name="n">Liczba wierzchołków</param>
        /// <param name="density">Prawdopodobieństwo istnienia krawędzi</param>
        /// <returns>Utworzony graf</returns>
        /// <remarks>
        /// Tworzony graf nie zawiera pętli, prawdopodonieństwo istnienia krawędzi pomiedzy dowolnymi wierzchołkami wynosi <i>density</i>.<br/>
        /// Oczekiwana liczba krawędzi wynosi <i>density</i>*n*(n-1)/2<br/>
        /// Gęstość <i>density</i> musi być z przedziału [0,1].
        /// </remarks>
        public IGraph UndirectedGraph(System.Type tg, int n, double density)
            {
            return UndirectedGraph(tg,n,density,1,1);
            }

        /// <summary>
        /// Tworzy ważony graf skierowany
        /// </summary>
        /// <param name="tg">Sposób reprezentacji grafu</param>
        /// <param name="n">Liczba wierzchołków</param>
        /// <param name="density">Prawdopodobieństwo istnienia krawędzi</param>
        /// <param name="wMin">Dolna granica wagi krawędzi</param>
        /// <param name="wMax">Górna granica wagi krawędzi</param>
        /// <returns>Utworzony graf</returns>
        /// <remarks>
        /// Tworzony graf nie zawiera pętli, prawdopodonieństwo istnienia krawędzi pomiedzy dowolnymi wierzchołkami wynosi <i>density</i>.<br/>
        /// Oczekiwana liczba krawędzi wynosi <i>density</i>*n*(n-1)<br/>
        /// Wagi krawędzi są losowymi liczbami całkowitymi (rozkład jednostajny) z zakresu <i>wMin</i>..<i>wMax</i> (włącznie).<br/>
        /// Gęstość <i>density</i> musi być z przedziału [0,1].
        /// </remarks>
        public IGraph DirectedGraph(System.Type tg, int n, double density, int wMin, int wMax)
            {
            if ( density<0 || density>1 || wMin>wMax )
                throw new System.ArgumentException("Invalid random graph generator argument");
            ++wMax;
            IGraph g = Graph.IsolatedVerticesGraph(true,n,tg);
            for ( int i=0 ; i<n ; ++i )
                for ( int j=0 ; j<n ; ++j)
                    if ( i!=j && rand.NextDouble()<density)
                        g.AddEdge(i,j,rand.Next(wMin,wMax));
            return g;
            }

        /// <summary>
        /// Tworzy nieważony graf skierowany
        /// </summary>
        /// <param name="tg">Sposób reprezentacji grafu</param>
        /// <param name="n">Liczba wierzchołków</param>
        /// <param name="density">Prawdopodobieństwo istnienia krawędzi</param>
        /// <returns>Utworzony graf</returns>
        /// <remarks>
        /// Tworzony graf nie zawiera pętli, prawdopodonieństwo istnienia krawędzi pomiedzy dowolnymi wierzchołkami wynosi <i>density</i>.<br/>
        /// Oczekiwana liczba krawędzi wynosi <i>density</i>*n*(n-1)<br/>
        /// Gęstość <i>density</i> musi być z przedziału [0,1].
        /// </remarks>
        public IGraph DirectedGraph(System.Type tg, int n, double density)
            {
            return DirectedGraph(tg,n,density,1,1);
            }

        /// <summary>
        /// Tworzy ważony skierowany graf acykliczny (DAG)
        /// </summary>
        /// <param name="tg">Sposób reprezentacji grafu</param>
        /// <param name="n">Liczba wierzchołków</param>
        /// <param name="density">Prawdopodobieństwo istnienia krawędzi</param>
        /// <param name="wMin">Dolna granica wagi krawędzi</param>
        /// <param name="wMax">Górna granica wagi krawędzi</param>
        /// <returns>Utworzony graf</returns>
        /// <remarks>
        /// Prawdopodonieństwo istnienia krawędzi pomiedzy dowolnymi wierzchołkami wynosi <i>density</i>.<br/>
        /// Oczekiwana liczba krawędzi wynosi <i>density</i>*n*(n-1)/2<br/>
        /// Wagi krawędzi są losowymi liczbami całkowitymi (rozkład jednostajny) z zakresu <i>wMin</i>..<i>wMax</i> (włącznie).<br/>
        /// Gęstość <i>density</i> musi być z przedziału [0,1].
        /// </remarks>
        public IGraph DAG(System.Type tg, int n, double density, int wMin, int wMax)
            {
            if ( density<0 || density>1 || wMin>wMax )
                throw new System.ArgumentException("Invalid random graph generator argument");
            ++wMax;
            IGraph g = Graph.IsolatedVerticesGraph(true,n,tg);
            for ( int i=0 ; i<n ; ++i )
                for ( int j=i+1 ; j<n ; ++j)
                    if ( rand.NextDouble()<density)
                        g.AddEdge(i,j,rand.Next(wMin,wMax));
            return Permute(g);
            }

        /// <summary>
        /// Tworzy nieskierowany graf euklidesowy
        /// </summary>
        /// <param name="tg">Sposób reprezentacji grafu</param>
        /// <param name="n">Liczba wierzchołków</param>
        /// <param name="density">Prawdopodobieństwo istnienia krawędzi</param>
        /// <param name="xMin">Dolna granica wartości współrzędnej x</param>
        /// <param name="xMax">Górna granica wartości współrzędnej x</param>
        /// <param name="yMin">Dolna granica wartości współrzędnej y</param>
        /// <param name="yMax">Górna granica wartości współrzędnej y</param>
        /// <returns>Utworzony graf</returns>
        /// <remarks>
        /// Tworzony graf nie zawiera pętli, prawdopodonieństwo istnienia krawędzi pomiedzy dowolnymi wierzchołkami wynosi <i>density</i>.<br/>
        /// Oczekiwana liczba krawędzi wynosi <i>density</i>*n*(n-1)/2<br/>
        /// Wagi krawędzi odpowiadają odległościom euklidesowym między wierzchołkami rozmieszczonymi losowo na płaszczyznie
        /// (zaokrąglonym w górę do wartości całkowitej), rozkład punktów jednostajny na obszarze [xMin,xMax]*[yMin,yMax].<br/>
        /// Gęstość <i>density</i> musi być z przedziału [0,1].
        /// </remarks>
        public IGraph UndirectedEuclidGraph(System.Type tg, int n, double density, double xMin, double xMax, double yMin, double yMax)
            {
            if ( density<0 || density>1 || xMin>=xMax || yMin>=yMax )
                throw new System.ArgumentException("Invalid random graph generator argument");
            double w;
            double[] x = new double[n];
            double[] y = new double[n];
            IGraph g = Graph.IsolatedVerticesGraph(false,n,tg);
            for (int i=0 ; i<n ; ++i )
                {
                x[i] = rand.NextDouble()*(xMax-xMin)+xMin;
                y[i] = rand.NextDouble()*(yMax-yMin)+yMin;
                }
            for ( int i=0 ; i<n ; ++i )
                for ( int j=i+1 ; j<n ; ++j)
                    if ( rand.NextDouble()<density)
                        {
                        w=System.Math.Sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) );
                        g.AddEdge(i,j,(int)System.Math.Ceiling(w));
                        }
            return g;
            }

        /// <summary>
        /// Tworzy ważony graf dwudzielny
        /// </summary>
        /// <param name="tg">Sposób reprezentacji grafu</param>
        /// <param name="n">Liczba wierzchołków w pierwszym podzbiorze</param>
        /// <param name="m">Liczba wierzchołków w drugim podzbiorze</param>
        /// <param name="density">Prawdopodobieństwo istnienia krawędzi</param>
        /// <param name="wMin">Dolna granica wagi krawędzi</param>
        /// <param name="wMax">Górna granica wagi krawędzi</param>
        /// <returns>Utworzony graf</returns>
        /// <remarks>
        /// Tworzony graf ma <i>n</i>+<i>m</i> wierzchołków, jest to nieskierowany graf (n,m)-dwudzielny.<br/>
        /// Prawdopodonieństwo istnienia krawędzi pomiedzy wierzchołkami z róznych podzbiorów wynosi <i>density</i>.<br/>
        /// Oczekiwana liczba krawędzi wynosi <i>density</i>*n*m/2<br/>
        /// Wagi krawędzi są losowymi liczbami całkowitymi (rozkład jednostajny) z zakresu <i>wMin</i>..<i>wMax</i> (włącznie).<br/>
        /// Gęstość <i>density</i> musi być z przedziału [0,1].
        /// </remarks>
        public IGraph BipariteGraph(System.Type tg, int n, int m, double density, int wMin, int wMax)
            {
            if ( density<0 || density>1 || wMin>wMax )
                throw new System.ArgumentException("Invalid random graph generator argument");
            ++wMax;
            IGraph g = Graph.IsolatedVerticesGraph(false,n+m,tg);
            for ( int i=0 ; i<n ; ++i )
                for ( int j=n ; j<n+m ; ++j)
                    if ( rand.NextDouble()<density)
                        g.AddEdge(i,j,rand.Next(wMin,wMax));
            return Permute(g);
            }

        /// <summary>
        /// Tworzy nieważony graf dwudzielny
        /// </summary>
        /// <param name="tg">Sposób reprezentacji grafu</param>
        /// <param name="n">Liczba wierzchołków w pierwszym podzbiorze</param>
        /// <param name="m">Liczba wierzchołków w drugim podzbiorze</param>
        /// <param name="density">Prawdopodobieństwo istnienia krawędzi</param>
        /// <returns>Utworzony graf</returns>
        /// <remarks>
        /// Tworzony graf ma <i>n</i>+<i>m</i> wierzchołków, jest to nieskierowany graf (n,m)-dwudzielny.<br/>
        /// Prawdopodonieństwo istnienia krawędzi pomiedzy wierzchołkami z róznych podzbiorów wynosi <i>density</i>.<br/>
        /// Oczekiwana liczba krawędzi wynosi <i>density</i>*n*m/2<br/>
        /// Gęstość <i>density</i> musi być z przedziału [0,1].
        /// </remarks>
        public IGraph BipariteGraph(System.Type tg, int n, int m, double density)
            {
            return BipariteGraph(tg,n,m,density,1,1);
            }

        /// <summary>
        /// Tworzy ważony graf eulerowski
        /// </summary>
        /// <param name="tg">Sposób reprezentacji grafu</param>
        /// <param name="directed">Informacja czy graf jest skierowany</param>
        /// <param name="n">Liczba wierzchołków</param>
        /// <param name="dMin">Dolna granica stopnia wierzchołka</param>
        /// <param name="dMax">Górna granica stopnia wierzchołka</param>
        /// <param name="wMin">Dolna granica wagi krawędzi</param>
        /// <param name="wMax">Górna granica wagi krawędzi</param>
        /// <returns>Utworzony graf</returns>
        /// <remarks>
        /// Tworzony graf nie zawiera pętli<br/>
        /// Wagi krawędzi są losowymi liczbami całkowitymi (rozkład jednostajny) z zakresu <i>wMin</i>..<i>wMax</i> (włącznie).<br/>
        /// Stopnie wierzchołków są losowymi liczbami całkowitymi (rozkład jednostajny) z zakresu <i>dMin</i>..<i>dMax</i> (włącznie).
        /// Dla grafów nieskierowanych parametry <i>dMin</i> i <i>dMax</i> muszą być parzyste.<br/>
        /// Metoda może działać bardzo długo (zawiera losowanie "do skutku").
        /// </remarks>
        public IGraph EulerGraph(System.Type tg, bool directed, int n, int dMin, int dMax, int wMin, int wMax)
            {
            int dtarget, deg, idx;
            var vUsedFrom = new System.Collections.Generic.List<int>();
            var vUsedTo = new System.Collections.Generic.List<int>();
        
            if ( directed )
                {
                if ( dMin<1 || dMax<dMin || dMax>n )
                    throw new System.ArgumentException("Invalid dMin or dMax parameter for Euler random graph generator");
                }
            else
                {
                if ( (dMin&1)==1 || (dMax&1)==1 || dMin<2 || dMax<dMin || dMax>n )
                    throw new System.ArgumentException("For undirected grahp parameters dMin and dMax have to be positive even numbers");
                }
            IGraph g = Graph.IsolatedVerticesGraph(directed,n,tg);
            ++wMax;
            // startujemy z grafu pełnego o dmax+1 wierzchołkach
            for ( int i=0 ; i<dMax+1 ; ++i )
                for ( int j=0 ; j<i ; ++j )
                    {
                    g.AddEdge(i,j,rand.Next(wMin,wMax));
                    if (directed) g.AddEdge(j,i,rand.Next(wMin,wMax));
                    }

            for ( int i=dMax+1 ; i<n ; ++i )
                {
                // uwaga - graf złożony z wierzchołków 0..i-1 jest już eulerowski
                dtarget = directed ?                      // docelowy stopień wierzchołka i
                              rand.Next(dMin,dMax+1) : 
                              dMin + rand.Next(1+(dMax-dMin)/2)*2 ;
                deg=0;
                vUsedFrom.Clear();
                vUsedTo.Clear();
                vUsedFrom.Add(i);
                vUsedTo.Add(i);
                do
                    {
                    // weź dowolną krawędź z podgrafu{0..i-1}
                    idx = rand.Next(0, i);
                    foreach ( Edge e in g.OutEdges(idx) )
                        {
                        if ( !vUsedFrom.Contains(e.from) && !vUsedTo.Contains(e.to) )
                            {
                            // zastąp tę krawędź dwoma nowymi krawędziami
                            g.DelEdge(e.from,e.to);
                            g.AddEdge(e.from,i,rand.Next(wMin,wMax));
                            g.AddEdge(i,e.to,rand.Next(wMin,wMax));
                            ++deg;
                            vUsedFrom.Add(e.from);
                            vUsedTo.Add(e.to);
                            if ( !directed )
                                {
                                ++deg;
                                vUsedFrom.Add(e.to);
                                vUsedTo.Add(e.from);
                                }
                            break;
                            }
                        }
                    // oj, to może długo działać...
                    }
                while ( deg<dtarget );
                }
            
            return Permute(g);
            }

        /// <summary>
        /// Tworzy nieważony graf eulerowski
        /// </summary>
        /// <param name="tg">Sposób reprezentacji grafu</param>
        /// <param name="directed">Informacja czy graf jest skierowany</param>
        /// <param name="n">Liczba wierzchołków</param>
        /// <param name="dMin">Dolna granica stopnia wierzchołka</param>
        /// <param name="dMax">Górna granica stopnia wierzchołka</param>
        /// <returns>Utworzony graf</returns>
        /// <remarks>
        /// Tworzony graf nie zawiera pętli<br/>
        /// Stopnie wierzchołków są losowymi liczbami całkowitymi (rozkład jednostajny) z zakresu <i>dMin</i>..<i>dMax</i> (włącznie).
        /// Dla grafów nieskierowanych parametry <i>dMin</i> i <i>dMax</i> muszą być parzyste.<br/>
        /// Metoda może działać bardzo długo (zawiera losowanie "do skutku").
        /// </remarks>
        public IGraph EulerGraph(System.Type tg, bool directed, int n, int dMin, int dMax)
            {
            return EulerGraph(tg,directed,n,dMin,dMax,1,1);
            }

        /// <summary>
        /// Tworzy ważony graf półeulerowski
        /// </summary>
        /// <param name="tg">Sposób reprezentacji grafu</param>
        /// <param name="directed">Informacja czy graf jest skierowany</param>
        /// <param name="n">Liczba wierzchołków</param>
        /// <param name="dMin">Dolna granica stopnia wierzchołka</param>
        /// <param name="dMax">Górna granica stopnia wierzchołka</param>
        /// <param name="wMin">Dolna granica wagi krawędzi</param>
        /// <param name="wMax">Górna granica wagi krawędzi</param>
        /// <returns>Utworzony graf</returns>
        /// <remarks>
        /// Tworzony graf nie zawiera pętli<br/>
        /// Wagi krawędzi są losowymi liczbami całkowitymi (rozkład jednostajny) z zakresu <i>wMin</i>..<i>wMax</i> (włącznie).<br/>
        /// Stopnie wierzchołków są losowymi liczbami całkowitymi (rozkład jednostajny) z zakresu <i>dMin</i>..<i>dMax</i> (włącznie).
        /// Dla grafów nieskierowanych parametry <i>dMin</i> i <i>dMax</i> muszą być parzyste.<br/>
        /// Metoda może działać bardzo długo (zawiera losowanie "do skutku").<br/>
        /// Graf powstaje przez usunięcie jednej krawędzi z grafu eulerowskiego, więc dla dwóch wierzchołków stopnie mogą być niższe niż<i> dMin</i>.
        /// </remarks>
        public IGraph SemiEulerGraph(System.Type tg, bool directed, int n, int dMin, int dMax, int wMin, int wMax)
            {
            IGraph g = EulerGraph(tg,directed,n,dMin,dMax,wMin,wMax);
            Edge e = g.OutEdges(0).First();
            g.DelEdge(e.from,e.to);
            return Permute(g);
            }

        /// <summary>
        /// Tworzy nieważony graf półeulerowski
        /// </summary>
        /// <param name="tg">Sposób reprezentacji grafu</param>
        /// <param name="directed">Informacja czy graf jest skierowany</param>
        /// <param name="n">Liczba wierzchołków</param>
        /// <param name="dMin">Dolna granica stopnia wierzchołka</param>
        /// <param name="dMax">Górna granica stopnia wierzchołka</param>
        /// <returns>Utworzony graf</returns>
        /// <remarks>
        /// Tworzony graf nie zawiera pętli<br/>
        /// Stopnie wierzchołków są losowymi liczbami całkowitymi (rozkład jednostajny) z zakresu <i>dMin</i>..<i>dMax</i> (włącznie).
        /// Dla grafów nieskierowanych parametry <i>dMin</i> i <i>dMax</i> muszą być parzyste.<br/>
        /// Metoda może działać bardzo długo (zawiera losowanie "do skutku").<br/>
        /// Graf powstaje przez usunięcie jednej krawędzi z grafu eulerowskiego, więc dla dwóch wierzchołków stopnie mogą być niższe niż<i> dMin</i>.
        /// </remarks>
        public IGraph SemiEulerGraph(System.Type tg, bool directed, int n, int dMin, int dMax)
            {
            return SemiEulerGraph(tg,directed,n,dMin,dMax,1,1);
            }

        /// <summary>
        /// Tworzy ważone drzewo nieskierowane
        /// </summary>
        /// <param name="tg">Sposób reprezentacji grafu (drzewa)</param>
        /// <param name="n">Liczba wierzchołków</param>
        /// <param name="density">Prawdopodobieństwo istnienia krawędzi</param>
        /// <param name="wMin">Dolna granica wagi krawędzi</param>
        /// <param name="wMax">Górna granica wagi krawędzi</param>
        /// <returns>Utworzony graf (drzewo)</returns>
        /// <remarks>
        /// Tworzony graf jest drzewem (lasem).<br/>
        /// Oczekiwana liczba krawędzi wynosi <i>density</i>*(n-1)<br/>
        /// Wagi krawędzi są losowymi liczbami całkowitymi (rozkład jednostajny) z zakresu <i>wMin</i>..<i>wMax</i> (włącznie).<br/>
        /// Gęstość <i>density</i> musi być z przedziału [0,1].
        /// </remarks>
        public IGraph TreeGraph(System.Type tg, int n, double density, int wMin, int wMax)
            {
            int i, j, ii, jj;
            if ( density<0 || density>1 || wMin>wMax )
                throw new System.ArgumentException("Invalid random graph generator argument");
            ++wMax;
            IGraph g = Graph.IsolatedVerticesGraph(false,n,tg);
            var hs = new System.Collections.Generic.HashSet<System.Collections.Generic.HashSet<int>>();
            for ( int k=0 ; k<n ; ++k )
                hs.Add(new System.Collections.Generic.HashSet<int>(){k} );
            
            for ( int k=1 ; k<n ; ++k )
                if ( rand.NextDouble()<density)
                    {
                    i=rand.Next(hs.Count);
                    j=rand.Next(hs.Count-1);
                    if ( j>=i ) ++j;
                    ii=hs.ElementAt(i).ElementAt(rand.Next(hs.ElementAt(i).Count));
                    jj=hs.ElementAt(j).ElementAt(rand.Next(hs.ElementAt(j).Count));
                    g.AddEdge(ii,jj, rand.Next(wMin,wMax));
                    hs.ElementAt(i).Union(hs.ElementAt(j));
                    hs.ElementAt(j).Clear();
                    hs.RemoveWhere(x=>x.Count==0);
                    }
            return g;
            }

        /// <summary>
        /// Tworzy nieważone drzewo nieskierowane
        /// </summary>
        /// <param name="tg">Sposób reprezentacji grafu (drzewa)</param>
        /// <param name="n">Liczba wierzchołków</param>
        /// <param name="density">Prawdopodobieństwo istnienia krawędzi</param>
        /// <returns>Utworzony graf (drzewo)</returns>
        /// <remarks>
        /// Tworzony graf jest drzewem (lasem).<br/>
        /// Oczekiwana liczba krawędzi wynosi <i>density</i>*(n-1)<br/>
        /// Gęstość <i>density</i> musi być z przedziału [0,1].
        /// </remarks>
        public IGraph TreeGraph(System.Type tg, int n, double density)
            {
            return TreeGraph(tg,n,density,1,1);
            }

	    }  //  class RandomGraphGenerator

}
